1// Copyright 2017 The Wuffs Authors. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// https://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package ast 16 17import ( 18 t "github.com/google/wuffs/lang/token" 19) 20 21func TopologicalSortStructs(ns []*Struct) (sorted []*Struct, ok bool) { 22 // Algorithm is a depth-first search as per 23 // https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search 24 sorted = make([]*Struct, 0, len(ns)) 25 byQID := map[t.QID]*Struct{} 26 for _, n := range ns { 27 byQID[n.QID()] = n 28 } 29 marks := map[*Struct]uint8{} 30 for _, n := range ns { 31 if _, ok := marks[n]; !ok { 32 sorted, ok = tssVisit(sorted, n, byQID, marks) 33 if !ok { 34 return nil, false 35 } 36 } 37 } 38 return sorted, true 39} 40 41func tssVisit(dst []*Struct, n *Struct, byQID map[t.QID]*Struct, marks map[*Struct]uint8) ([]*Struct, bool) { 42 const ( 43 unmarked = 0 44 temporary = 1 45 permanent = 2 46 ) 47 switch marks[n] { 48 case temporary: 49 return nil, false 50 case permanent: 51 return dst, true 52 } 53 marks[n] = temporary 54 55 for _, f := range n.Fields() { 56 x := f.AsField().XType().Innermost() 57 if o := byQID[x.QID()]; o != nil { 58 var ok bool 59 dst, ok = tssVisit(dst, o, byQID, marks) 60 if !ok { 61 return nil, false 62 } 63 } 64 } 65 66 marks[n] = permanent 67 return append(dst, n), true 68} 69