import chalk from 'chalk' ; import { List , Map , Record , Set } from 'immutable' ; import { FilePathStore } from '../service/executionPaths' ; import { PyteaService } from '../service/pyteaService' ; import { formatCodeSource } from '../service/pyteaUtils' ; import { absIndexByLen , sanitizeSource } from './backUtils' ; import { ConstraintSolver , expToCtr } from './constraintSolver' ; import { CompareConstraintType , Constraint , ConstraintIndex , ConstraintType , CtrAnd , CtrBroad , CtrExpBool , CtrFail , CtrForall , CtrNot , CtrOr , ctrToStr , EqualityConstraint , NumConstraint , } from './constraintType' ; import { isStructuallyEq , simplifyConstraint , simplifyExp } from './expUtils' ; import { NumRange } from './range' ; import { CodeSource } from './sharpValues' ; import { BoolOpType , ExpBool , ExpNum , ExpShape , ExpShapeConst , ExpString , NumBopType , NumOpType , NumUopType , SEType , ShapeOpType , StringOpType , SymbolIndex , SymbolType , SymBool , SymExp , SymFloat , SymInt , SymShape , SymString , SymVal , } from './symExpressions' ; export interface ConstraintGen { genSymInt ( name , source ) : SymInt ; genSymFloat ( name , source ) : SymFloat ; genSymBool ( name , source ) : SymBool ; genSymString ( name , source ) : SymString ; genSymShape ( name , rank , source ) : SymShape ; genSymIntGte ( name , min , source ) : CSReturn < SymInt > ; genSymIntEq ( name , min , source ) : CSReturn < SymInt > ; genSymFloatGte ( name , min , source ) : CSReturn < SymFloat > ; genShaped ( name , rank , dims , source ) : CSReturn < ExpShapeConst > ; genFromBool ( exp , source ) : CtrExpBool ; genEquality ( type , left , right , source ) : EqualityConstraint ; genNumCompare ( type , left , right , source ) : NumConstraint | EqualityConstraint ; genAnd ( left , right , source ) : CtrAnd ; genOr ( left , right , source ) : CtrOr ; genNot ( constraint , source ) : CtrNot ; genBroad ( left , right , source ) : CtrBroad ; genForall ( symbol , range , constraint , source ) : CtrForall ; genFail ( reason , source ) : CtrFail ; } class IdManager { ctrIdMax : ConstraintIndex ; symIdMax : SymbolIndex ; constructor ( ) { this . ctrIdMax = 0 ; this . symIdMax = 0 ; } getCtrId ( ) { return ++ this . ctrIdMax ; } getSymId ( ) { return ++ this . symIdMax ; } } interface ConstraintSetProps { readonly idManager : IdManager ; readonly ctrPool : List < Constraint > ; readonly hardCtr : List < number > ; readonly softCtr : List < number > ; readonly pathCtr : List < number > ; readonly notPrunedCtrMax : number ; readonly ctrIdCache : Set < ConstraintIndex > ; readonly rangeCache : Map < SymbolIndex , NumRange > ; readonly stringCache : Map < SymbolIndex , string > ; readonly nonStringCache : Map < SymbolIndex , Set < string > > ; readonly valid : boolean | undefined ; } const constraintSetDefaults = { idManager : new IdManager ( ) , ctrPool : List ( ) , hardCtr : List ( ) , softCtr : List ( ) , pathCtr : List ( ) , notPrunedCtrMax : - 1 , ctrIdCache : Set ( ) , rangeCache : Map < number , NumRange > ( ) , stringCache : Map < number , string > ( ) , nonStringCache : Map < number , Set < string > > ( ) , valid : true , } ; export type CSReturnE < T > = [ T , ConstraintSet ] | string ; export type CSReturn < T > = [ T , ConstraintSet ] ; export class ConstraintSet extends Record ( constraintSetDefaults ) implements ConstraintSetProps , ConstraintGen { constructor ( params ? ) { params ? super ( params ) : super ( ) ; } toString ( pathStore ? ) { return this . ctrPool . map ( ( ctr ) => simplifyConstraint ( this , ctr ) ) . map ( ( ctr , idx ) => { const str = ctrToStr ( ctr ) ; const source = formatCodeSource ( ctr . source , pathStore ) ; const result = `${ idx + 1 }: ${ str } - ${ source }` ; if ( this . hardCtr . contains ( idx ) ) { return chalk . gray ( result ) ; } else if ( this . pathCtr . contains ( idx ) ) { return chalk . yellow ( result ) ; } else { return result ; } } ) . join ( '\n' ) ; } count ( ) { return this . ctrPool . count ( ) ; } getConstraints ( ) { return this . ctrPool . map ( ( ctr ) => simplifyConstraint ( this , ctr ) ) . toArray ( ) ; } getConstraintObject ( pathStore ? ) { const ctrList = this . getConstraints ( ) . map ( ( ctr ) => { const codePos = formatCodeSource ( ctr . source , pathStore ) ; const str = ctrToStr ( simplifyConstraint ( this , ctr ) ) ; if ( codePos ) { ctr . message = `${ ctr . message ?? '-' } at <${ codePos }>\n  ${ str }` ; } else { ctr . message = `constraint at <${ codePos }>\n  ${ str }` ; } return ctr ; } ) ; return { ctrPool : sanitizeSource ( ctrList , pathStore ) , hardCtr : this . hardCtr . toArray ( ) , softCtr : this . softCtr . toArray ( ) , pathCtr : this . pathCtr . toArray ( ) , } ; } getConstraintJSON ( pathStore ? ) { return JSON . stringify ( this . getConstraintObject ( pathStore ) ) ; } require ( constraint ) { const immCheck = this . checkImmediate ( constraint ) ; if ( immCheck === true ) { return this ; } else if ( immCheck === false ) { return this . set ( 'valid' , false ) . _pushSoft ( constraint ) ; } return this . _pushSoft ( constraint ) ; } requireAll ( constraint ) { let cs = this ; constraint . forEach ( ( ctr ) => { cs = cs . require ( ctr ) ; } ) ; return cs ; } guarantee ( constraint ) { const immCheck = this . checkImmediate ( constraint ) ; if ( immCheck === true ) { return this ; } else if ( immCheck === false ) { return this . set ( 'valid' , false ) . _pushHard ( constraint ) ; } return this . _cacheConstraint ( constraint ) . _pushHard ( constraint ) ; } guaranteeAll ( constraint ) { let cs = this ; constraint . forEach ( ( ctr ) => { cs = cs . guarantee ( ctr ) ; } ) ; return cs ; } addIf ( constraint ) { const immCheck = this . checkImmediate ( constraint ) ; if ( immCheck === true ) { return this ; } else if ( immCheck === false ) { return this . set ( 'valid' , false ) . _pushPath ( constraint ) ; } return this . _cacheConstraint ( constraint ) . _pushPath ( constraint ) ; } addIfAll ( constraint ) { let cs = this ; constraint . forEach ( ( ctr ) => { cs = cs . addIf ( ctr ) ; } ) ; return cs ; } genSymInt ( name , source ) { const id = this . _getNextSymId ( ) ; return { type : SymbolType . Int , id , name : `${ name }_I${ id }` , source , } ; } genSymFloat ( name , source ) { const id = this . _getNextSymId ( ) ; return { type : SymbolType . Float , id , name : `${ name }_F${ id }` , source , } ; } genSymBool ( name , source ) { const id = this . _getNextSymId ( ) ; return { type : SymbolType . Bool , id , name : `${ name }_B${ id }` , source , } ; } genSymString ( name , source ) { const id = this . _getNextSymId ( ) ; return { type : SymbolType . String , id , name : `${ name }_Str${ id }` , source , } ; } genSymShape ( name , rank , source ) { const id = this . _getNextSymId ( ) ; return { type : SymbolType . Shape , id , name : `${ name }_Shp${ id }` , rank , source , } ; } genSymIntGte ( name , min , source ) { const newSym = this . genSymInt ( name , source ) ; const comp = this . genNumCompare ( ConstraintType . LessThanOrEqual , ExpNum . fromSymbol ( newSym ) , SymExp . fromConst ( min ) as ExpNum , source ) ; return [ newSym , this . guarantee ( comp ) ] ; } genSymIntEq ( name , value , source ) { const newSym = this . genSymInt ( name , source ) ; const exp = SymExp . fromConst ( value ) as ExpNum ; const ctr = this . genEquality ( ConstraintType . Equal , ExpNum . fromSymbol ( newSym ) , exp , source ) ; const range = this . getCachedRange ( value ) ; if ( range ?. valid ( ) ) { const cache = this . rangeCache . set ( newSym . id , range ) ; const newCtr = this . set ( 'rangeCache' , cache ) ; return [ newSym , newCtr . _pushHard ( ctr ) ] ; } else { return [ newSym , this . guarantee ( ctr ) ] ; } } genSymFloatGte ( name , min , source ) { const newSym = this . genSymFloat ( name , source ) ; const comp = this . genNumCompare ( ConstraintType . LessThanOrEqual , ExpNum . fromSymbol ( newSym ) , SymExp . fromConst ( min ) as ExpNum , source ) ; return [ newSym , this . guarantee ( comp ) ] ; } genShaped ( name , rank , dims , source ) { if ( rank < 0 ) { throw `making shape '${ name } got negative rank ${ rank }` ; } let cs = this ; const newDims = [ ] ; if ( ! dims ) { for ( let i = 0 ; i < rank ; i ++ ) { const [ newDim , newCs ] = this . genSymIntGte ( `${ name }_dim${ i }` , 0 , source ) ; cs = newCs ; const dimExp = ExpNum . fromSymbol ( newDim ) ; newDims . push ( dimExp ) ; } } else { for ( const dim of dims ) { if ( typeof dim === 'number' ) { newDims . push ( ExpNum . fromConst ( dim , source ) ) ; } else { newDims . push ( dim ) ; } } } return [ ExpShape . fromConst ( rank , newDims , source ) , cs ] ; } castBoolToInt ( exp , source ) { if ( typeof exp === 'boolean' ) { return [ + exp , this ] ; } if ( exp . opType === BoolOpType . Const ) { return [ exp . value ? 1 : 0 , this as ConstraintSet ] ; } const isTrue = this . checkImmediate ( exp ) ; if ( isTrue !== undefined ) { return [ isTrue ? 1 : 0 , this as ConstraintSet ] ; } const ctr = this . genFromBool ( exp , source ) ; const ctrNot = this . genNot ( ctr , source ) ; const num = ExpNum . fromSymbol ( this . genSymInt ( `num$castbool_${ ctr . id }` , source ) ) ; const numZero = this . genEquality ( ConstraintType . Equal , num , ExpNum . fromConst ( 0 , source ) , source ) ; const numOne = this . genEquality ( ConstraintType . Equal , num , ExpNum . fromConst ( 1 , source ) , source ) ; const finalCtr = this . genOr ( this . genAnd ( ctr , numOne , source ) , this . genAnd ( ctrNot , numZero , source ) , source ) ; return [ num , this . guarantee ( finalCtr ) ] ; } castNumToBool ( exp , source ) { if ( typeof exp === 'number' ) { return [ ! ! exp , this ] ; } const range = this . getCachedRange ( exp ) ; if ( range === undefined ) { return 'castNumToBool: exp is non-numeric' ; } if ( range . gt ( 0 ) || range . lt ( 0 ) ) return [ true , this ] ; else if ( range . eq ( 0 ) ) return [ false , this ] ; const isZero = this . genEquality ( ConstraintType . Equal , exp , ExpNum . fromConst ( 0 , source ) , source ) ; const isNZero = this . genEquality ( ConstraintType . NotEqual , exp , ExpNum . fromConst ( 0 , source ) , source ) ; const sym = this . genSymBool ( `bool$castnum_${ isZero . id }` , source ) ; const expSym = ExpBool . fromSymbol ( sym ) ; const ctrSym = this . genFromBool ( expSym , source ) ; const finalCtr = this . genOr ( this . genAnd ( ctrSym , isNZero , source ) , this . genAnd ( this . genNot ( ctrSym , source ) , isZero , source ) , source ) ; return [ expSym , this . guarantee ( finalCtr ) ] ; } genFromBool ( exp , source ) { const id = this . _getNextCtrId ( ) ; return { type : ConstraintType . ExpBool , id , exp , source , } ; } genEquality ( type , left , right , source ) { if ( left . expType === SEType . Num && right . expType === SEType . Num ) { return this . genNumCompare ( type , left , right , source ) as EqualityConstraint ; } const id = this . _getNextCtrId ( ) ; const constraint = { type , id , left , right , source , } ; return constraint ; } genNumCompare ( type , left , right , source ) { const id = this . _getNextCtrId ( ) ; left = typeof left === 'number' ? ExpNum . fromConst ( left , source ) : left ; right = typeof right === 'number' ? ExpNum . fromConst ( right , source ) : right ; const constraint = { type , id , left , right , source , } ; return constraint ; } genAnd ( left , right , source ) { const id = this . _getNextCtrId ( ) ; const constraint = { type : ConstraintType . And , id , left , right , source , } ; return constraint ; } genOr ( left , right , source ) { const id = this . _getNextCtrId ( ) ; const constraint = { type : ConstraintType . Or , id , left , right , source , } ; return constraint ; } genNot ( constraint , source ) { const id = this . _getNextCtrId ( ) ; const notCtr = { type : ConstraintType . Not , id , constraint , source , } ; return notCtr ; } genBroad ( left , right , source ) { const id = this . _getNextCtrId ( ) ; const constraint = { type : ConstraintType . Broadcastable , id , left , right , source , } ; return constraint ; } genForall ( symbol , range , constraint , source ) { const id = this . _getNextCtrId ( ) ; const expRange = [ typeof range [ 0 ] === 'number' ? ExpNum . fromConst ( range [ 0 ] , source ) : range [ 0 ] , typeof range [ 1 ] === 'number' ? ExpNum . fromConst ( range [ 1 ] , source ) : range [ 1 ] , ] ; return { type : ConstraintType . Forall , id , symbol , range : expRange , constraint , source , } ; } genFail ( reason , source ) { const id = this . _getNextCtrId ( ) ; const failCtr = { type : ConstraintType . Fail , id , reason , source , } ; return failCtr ; } getCachedRange ( exp ) { if ( typeof exp === 'number' ) { return NumRange . fromConst ( exp ) ; } switch ( exp . opType ) { case NumOpType . Const : return NumRange . fromConst ( exp . value ) ; case NumOpType . Uop : { const baseRng = this . getCachedRange ( exp . baseValue ) ; if ( ! baseRng ) return undefined ; let rng ; switch ( exp . uopType ) { case NumUopType . Neg : rng = baseRng . neg ( ) ; break ; case NumUopType . Ceil : rng = baseRng . ceil ( ) ; break ; case NumUopType . Floor : rng = baseRng . floor ( ) ; break ; case NumUopType . Abs : rng = baseRng . abs ( ) ; break ; } return rng ?. valid ( ) ? rng : undefined ; } case NumOpType . Bop : { const leftRng = this . getCachedRange ( exp . left ) ; const rightRng = this . getCachedRange ( exp . right ) ; if ( ! leftRng || ! rightRng ) return undefined ; const calced = this . _calcRangeBop ( exp . bopType , leftRng , rightRng ) ; return calced . valid ( ) ? calced : undefined ; } case NumOpType . Symbol : { const cache = this . rangeCache . get ( exp . symbol . id ) ; if ( ! cache ) { return NumRange . genTop ( ) ; } return cache . valid ( ) ? cache : undefined ; } case NumOpType . Max : if ( exp . values . length === 0 ) { return undefined ; } else { const calced = exp . values . map ( ( num ) => this . getCachedRange ( num ) ) . reduce ( ( prevRng , currRng ) => { return currRng ? prevRng ?. max ( currRng ) : undefined ; } ) ; return calced ?. valid ( ) ? calced : undefined ; } case NumOpType . Min : if ( exp . values . length === 0 ) { return undefined ; } else { const calced = exp . values . map ( ( num ) => this . getCachedRange ( num ) ) . reduce ( ( prevRng , currRng ) => { return currRng ? prevRng ?. min ( currRng ) : undefined ; } ) ; return calced ?. valid ( ) ? calced : undefined ; } case NumOpType . Index : { const idxRng = this . getCachedRange ( exp . index ) ; if ( ! idxRng || ! idxRng . valid ( ) ) return ; if ( ! idxRng . isConst ( ) ) return NumRange . genGte ( 0 ) ; const idx = idxRng . start ; const shape = exp . baseShape ; switch ( shape . opType ) { case ShapeOpType . Const : if ( idx < shape . dims . length ) { return this . getCachedRange ( shape . dims [ idx ] ) ; } else { return ; } case ShapeOpType . Set : { const setIdx = this . getCachedRange ( shape . axis ) ; if ( ! setIdx ) return ; if ( setIdx . isConst ( ) && setIdx . start === idx ) return this . getCachedRange ( shape . dim ) ; if ( setIdx . contains ( idx ) ) return NumRange . genGte ( 0 ) ; return this . getCachedRange ( ExpNum . index ( shape . baseShape , idx , exp . source ) ) ; } case ShapeOpType . Concat : case ShapeOpType . Slice : case ShapeOpType . Broadcast : case ShapeOpType . Symbol : { const shapeCache = this . getCachedShape ( shape ) ; if ( ! shapeCache || idx >= shapeCache . length ) return ; return this . getCachedRange ( shapeCache [ idx ] ) ; } default : return ; } } case NumOpType . Numel : { const shape = this . getCachedShape ( exp . shape ) ; if ( shape ) { if ( shape . length === 0 ) return NumRange . fromConst ( 0 ) ; let rng = NumRange . fromConst ( 1 ) ; for ( const dim of shape ) { const dimRng = this . getCachedRange ( dim ) ; if ( ! dimRng ) { return ; } rng = rng . mul ( dimRng ) ; } if ( rng . valid ( ) ) return rng ; } return ; } } } getCachedShape ( exp ) { switch ( exp . opType ) { case ShapeOpType . Const : return exp . dims ; case ShapeOpType . Symbol : return ; case ShapeOpType . Set : { const base = this . getCachedShape ( exp . baseShape ) ; const axis = this . getCachedRange ( exp . axis ) ; if ( base && axis && axis . isConst ( ) && base . length > axis . end ) { const temp = base . slice ( ) ; temp [ axis . start ] = exp . dim ; return temp ; } return ; } case ShapeOpType . Slice : case ShapeOpType . Concat : case ShapeOpType . Broadcast : break ; } return ; } getCachedString ( exp ) { if ( typeof exp === 'string' ) { return exp ; } switch ( exp . opType ) { case StringOpType . Const : return exp . value ; case StringOpType . Concat : { const str1 = this . getCachedString ( exp . left ) ; const str2 = this . getCachedString ( exp . right ) ; if ( str1 !== undefined && str2 !== undefined ) { return str1 . concat ( str2 ) ; } break ; } case StringOpType . Slice : { const str = this . getCachedString ( exp . baseString ) ; if ( str === undefined ) break ; const strLen = str . length ; let start = 0 ; let end = strLen ; if ( exp . start !== undefined ) { const rngTemp = this . getCachedRange ( exp . start ) ; if ( rngTemp ?. isConst ( ) !== true ) break ; start = rngTemp . start ; } if ( exp . end !== undefined ) { const rngTemp = this . getCachedRange ( exp . end ) ; if ( rngTemp ?. isConst ( ) !== true ) break ; end = rngTemp . end ; } return str . slice ( absIndexByLen ( strLen , start ) , absIndexByLen ( strLen , end ) ) ; } case StringOpType . Symbol : if ( this . stringCache . has ( exp . symbol . id ) ) { return this . stringCache . get ( exp . symbol . id ) ; } break ; } return ; } checkNonString ( exp , tester ) { if ( typeof exp === 'string' ) { return exp !== tester ; } const strCache = this . getCachedString ( exp ) ; if ( strCache !== undefined ) { return strCache !== tester ; } if ( exp . opType === StringOpType . Symbol ) { const nonSet = this . nonStringCache . get ( exp . symbol . id ) ; if ( nonSet && nonSet . has ( tester ) ) { return true ; } } return ; } checkImmediate ( constraint ) { if ( ! PyteaService . shouldCheckImmediate ( ) ) { return ; } if ( 'expType' in constraint ) { if ( constraint . opType === BoolOpType . Const ) { return constraint . value ; } constraint = { type : ConstraintType . ExpBool , id : - 1 , exp : constraint , } as CtrExpBool ; } switch ( constraint . type ) { case ConstraintType . ExpBool : return this . checkImmediate ( expToCtr ( constraint . exp ) ) ; case ConstraintType . Equal : { const leftExp = simplifyExp ( this , constraint . left ) ; const rightExp = simplifyExp ( this , constraint . right ) ; if ( leftExp . expType === rightExp . expType ) { switch ( leftExp . expType ) { case SEType . Num : { const left = this . getCachedRange ( leftExp ) ; const right = this . getCachedRange ( rightExp as ExpNum ) ; if ( left && right && left . isConst ( ) && right . isConst ( ) ) return left . start === right . start ; } break ; case SEType . Bool : { let left ; let right ; switch ( leftExp . opType ) { case BoolOpType . Const : left = leftExp . value ; break ; case BoolOpType . Symbol : { const boolRange = this . getSymbolRange ( leftExp . symbol ) ; if ( boolRange ?. isConst ( ) ) { left = boolRange . start !== 0 ; } } break ; default : left = this . checkImmediate ( expToCtr ( leftExp ) ) ; break ; } const rightE = rightExp as ExpBool ; switch ( rightE . opType ) { case BoolOpType . Const : right = rightE . value ; break ; case BoolOpType . Symbol : { const boolRange = this . getSymbolRange ( rightE . symbol ) ; if ( boolRange ?. isConst ( ) ) { right = boolRange . start !== 0 ; } } break ; default : right = this . checkImmediate ( expToCtr ( rightE ) ) ; break ; } if ( left !== undefined && right !== undefined ) return left === right ; } break ; case SEType . Shape : { if ( leftExp . opType === ShapeOpType . Const && rightExp . expType === SEType . Shape && rightExp . opType === ShapeOpType . Const ) { if ( leftExp . dims . length !== rightExp . dims . length ) { return false ; } for ( let i = 0 ; i < leftExp . dims . length ; i ++ ) { const ld = leftExp . dims [ i ] ; const rd = rightExp . dims [ i ] ; if ( ld . opType === NumOpType . Const && rd . opType === NumOpType . Const && ld . value !== rd . value ) { return false ; } } } break ; } case SEType . String : default : break ; } const isStructEq = isStructuallyEq ( leftExp , rightExp ) ; if ( isStructEq ) return true ; return ; } return false ; } case ConstraintType . NotEqual : { const leftExp = simplifyExp ( this , constraint . left ) ; const rightExp = simplifyExp ( this , constraint . right ) ; if ( leftExp . expType === rightExp . expType ) { switch ( leftExp . expType ) { case SEType . Num : { const left = this . getCachedRange ( leftExp ) ; const right = this . getCachedRange ( rightExp as ExpNum ) ; if ( ! left || ! right ) return ; if ( left . isConst ( ) && right . isConst ( ) ) return ! ( left . start === right . start ) ; if ( left . ltRange ( right ) || right . ltRange ( left ) ) return true ; return undefined ; } case SEType . Bool : { const left = this . checkImmediate ( expToCtr ( leftExp ) ) ; const right = this . checkImmediate ( expToCtr ( rightExp as ExpBool ) ) ; if ( left !== undefined && right !== undefined ) return left !== right ; else return ; } case SEType . Shape : { const isStructEq = isStructuallyEq ( leftExp , rightExp ) ; if ( isStructEq ) return false ; } break ; case SEType . String : { const isStructEq = isStructuallyEq ( leftExp , rightExp ) ; if ( isStructEq ) return false ; } break ; default : return ; } return ; } return true ; } case ConstraintType . And : { const left = this . checkImmediate ( constraint . left ) ; if ( left === false ) return false ; const right = this . checkImmediate ( constraint . right ) ; if ( left === true ) return right ; return right === false ? false : undefined ; } case ConstraintType . Or : { const left = this . checkImmediate ( constraint . left ) ; if ( left === true ) return true ; const right = this . checkImmediate ( constraint . right ) ; if ( left === false ) return right ; return right === true ? true : undefined ; } case ConstraintType . Not : { const inner = this . checkImmediate ( constraint . constraint ) ; if ( inner === undefined ) return ; return ! inner ; } case ConstraintType . LessThan : { const left = this . getCachedRange ( constraint . left ) ; const right = this . getCachedRange ( constraint . right ) ; if ( ! left || ! right ) return ; return left . ltRange ( right ) ; } case ConstraintType . LessThanOrEqual : { const left = this . getCachedRange ( constraint . left ) ; const right = this . getCachedRange ( constraint . right ) ; if ( ! left || ! right ) return ; return left . lteRange ( right ) ; } case ConstraintType . Broadcastable : { const left = simplifyExp ( this , constraint . left ) ; const right = simplifyExp ( this , constraint . right ) ; if ( left . opType === ShapeOpType . Const && right . opType === ShapeOpType . Const ) { const [ baseShape , rightShape ] = left . rank < right . rank ? [ right , left ] : [ left , right ] ; const rankdiff = baseShape . dims . length - rightShape . dims . length ; for ( let i = 0 ; i < baseShape . dims . length ; i ++ ) { if ( i < rankdiff ) continue ; const dim = this . selectBroadcastable ( baseShape . dims [ i ] , rightShape . dims [ i - rankdiff ] ) ; if ( dim === false ) { return false ; } else if ( dim === undefined ) { return ; } } return true ; } } break ; case ConstraintType . Forall : return ; case ConstraintType . Fail : return false ; } return ; } selectBroadcastable ( left , right ) { const leftRng = this . getCachedRange ( left ) ; const rightRng = this . getCachedRange ( right ) ; if ( ! leftRng || ! rightRng ) return ; if ( leftRng . isConst ( ) ) { const ln = leftRng . start ; if ( ln === 1 ) return right ; if ( rightRng . isConst ( ) ) { if ( rightRng . start === 1 ) return left ; if ( ln !== rightRng . start ) return false ; return left ; } if ( ! rightRng . contains ( ln ) ) return false ; } if ( rightRng . isConst ( ) ) { const rn = rightRng . start ; if ( rn === 1 ) return left ; if ( ! leftRng . contains ( rn ) ) return false ; } if ( leftRng . intersect ( rightRng ) . valid ( ) === false ) return false ; if ( isStructuallyEq ( left , right ) ) return left ; return ; } getSymbolRange ( symbol ) { return this . rangeCache . get ( symbol . id ) ; } hasSingleVar ( constraint ) { switch ( constraint . type ) { case ConstraintType . ExpBool : return SymExp . hasSingleVar ( this , constraint . exp ) ; case ConstraintType . LessThan : case ConstraintType . LessThanOrEqual : case ConstraintType . Equal : case ConstraintType . NotEqual : { return SymExp . mergeSingleVar ( [ SymExp . hasSingleVar ( this , constraint . left ) , SymExp . hasSingleVar ( this , constraint . right ) , ] ) ; } case ConstraintType . And : case ConstraintType . Or : { return SymExp . mergeSingleVar ( [ this . hasSingleVar ( constraint . left ) , this . hasSingleVar ( constraint . right ) ] ) ; } case ConstraintType . Not : return this . hasSingleVar ( constraint . constraint ) ; case ConstraintType . Forall : case ConstraintType . Broadcastable : case ConstraintType . Fail : return true ; } } private _cacheConstraint ( constraint ) { const solver = new ConstraintSolver ( this ) ; return solver . solve ( constraint ) . ctrSet ; } private _calcRangeBop ( bopType , left , right ) { switch ( bopType ) { case NumBopType . Add : return left . add ( right ) ; case NumBopType . Sub : return left . sub ( right ) ; case NumBopType . Mul : return left . mul ( right ) ; case NumBopType . FloorDiv : return left . floordiv ( right ) ; case NumBopType . TrueDiv : return left . truediv ( right ) ; case NumBopType . Mod : return left . mod ( right ) ; } } private _pushHard ( constraint ) { let ctrSet = this ; if ( ! this . ctrIdCache . has ( constraint . id ) ) { ctrSet = ctrSet . set ( 'hardCtr' , ctrSet . hardCtr . push ( ctrSet . ctrPool . count ( ) ) ) ; ctrSet = ctrSet . set ( 'ctrPool' , ctrSet . ctrPool . push ( constraint ) ) ; ctrSet = ctrSet . set ( 'ctrIdCache' , ctrSet . ctrIdCache . add ( constraint . id ) ) ; } return ctrSet ; } private _pushSoft ( constraint ) { let ctrSet = this ; if ( ! this . ctrIdCache . has ( constraint . id ) ) { ctrSet = ctrSet . set ( 'softCtr' , ctrSet . softCtr . push ( ctrSet . ctrPool . count ( ) ) ) ; ctrSet = ctrSet . set ( 'ctrPool' , ctrSet . ctrPool . push ( constraint ) ) ; ctrSet = ctrSet . set ( 'ctrIdCache' , ctrSet . ctrIdCache . add ( constraint . id ) ) ; } return ctrSet ; } private _pushPath ( constraint ) { let ctrSet = this ; if ( ! this . ctrIdCache . has ( constraint . id ) ) { ctrSet = ctrSet . set ( 'pathCtr' , ctrSet . pathCtr . push ( ctrSet . ctrPool . count ( ) ) ) ; ctrSet = ctrSet . set ( 'ctrPool' , ctrSet . ctrPool . push ( constraint ) ) ; ctrSet = ctrSet . set ( 'ctrIdCache' , ctrSet . ctrIdCache . add ( constraint . id ) ) ; } return ctrSet ; } private _getNextCtrId ( ) { return this . idManager . getCtrId ( ) ; } private _getNextSymId ( ) { return this . idManager . getSymId ( ) ; } }